/*
 * Copyright (C) 2006 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package android.util;

import com.android.internal.util.ArrayUtils;
import com.android.internal.util.GrowingArrayUtils;

import libcore.util.EmptyArray;

/**
 * SparseArrays将整数映射到对象。与正常的对象数组不同，
 * 在索引中可能存在空白。它比使用HashMap将整数映射到对象更有效，因为它避免了自动装箱，
 * 而且它的数据结构不依赖于每个映射的额外的条目对象。
 *
 * 注意，这个容器在数组数据结构中保持它的映射，使用二进制搜索来查找键。
 * 该实现并不适合于包含大量项目的*数据结构*。它通常比传统的HashMap慢，
 * 因为查找需要一个二进制搜索，并且添加和删除需要插入和删除数组中的条目。
 * 对于持有数百个项目的容器，性能差异不显著，小于50%。
 * 
 *为了帮助性能，容器在删除键时包含了一个优化:它没有立即压缩它的数组，而是将被删除的条目标记为deleted。
 * 然后，该条目可以被重新用于相同的密钥，或者在以后的一个垃圾收集步骤中被压缩。
 * 这个垃圾收集将需要在任何时候执行该数组，或者检索映射大小或条目值。
 * 
 *可以在这个容器中使用{@link #keyAt(int)}和{@link #valueAt(int)}来迭代该容器中的项。使用 keyAt(int)对键进行迭代，索引的提升值将返回升序中的键
 * ，或者在valueAt(int)的情况下，在升序中对应于键的值。
 */
public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;

    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

    /**
     * 创建一个不包含映（mapping）射的新SparseArray。
     */
    public SparseArray() {
        this(10);
    }

    /**
     * 创建一个新的SparseArray，它不需要任何额外的内存分配来存储指定的映射数量。
     * 如果您提供初始容量为0，那么稀疏数组（SparseArray）将用一个轻量级表示来初始化，不需要额外的数组分配。
     *
     */
    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

    @Override
    @SuppressWarnings("unchecked")
    public SparseArray<E> clone() {
        SparseArray<E> clone = null;
        try {
            clone = (SparseArray<E>) super.clone();
            clone.mKeys = mKeys.clone();
            clone.mValues = mValues.clone();
        } catch (CloneNotSupportedException cnse) {
            /* ignore */
        }
        return clone;
    }

    /**
     * 获取从指定键映射的对象，如果没有这样的映射，则为null
     */
    public E get(int key) {
        return get(key, null);
    }

    /**
     * 获取从指定的键映射的对象，如果没有这样的映射，就返回指定值。
     */
    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }

    /**
     *从指定的键删除映射，如果有的话。
     */
    public void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

    /**
     *
     * {@link #delete(int)}别名
     */
    public void remove(int key) {
        delete(key);
    }

    /**
     * 删除指定索引处的映射。
     */
    public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

    /**
     * 批量删除，从index开始，删除size个
     *
     * @param index Index to begin at
     * @param size Number of mappings to remove
     */
    public void removeAtRange(int index, int size) {
        final int end = Math.min(mSize, index + size);
        for (int i = index; i < end; i++) {
            removeAt(i);
        }
    }

    private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        for (int i = 0; i < n; i++) {
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;

        // Log.e("SparseArray", "gc end with " + mSize);
    }

    /**
     * 将指定键的映射添加到指定的值，如果有的话，将从指定键替换之前的映射。
     */
    public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~i;

            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                gc();

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }

            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

    /**
     * 返回这个SparseArray 当前存储的键值映射的数量。
     */
    public int size() {
        if (mGarbage) {
            gc();
        }

        return mSize;
    }

    /**
     * 给定一个范围0. size()-1的索引，返回SparseArray存储的索引键值映射的键。
     *
     * 升序中与索引对应的键保证按升序排列，例如，keyAt(0)将返回*最小的键和keyAt(size()-1)将返回最大的*键。
     */
    public int keyAt(int index) {
        if (mGarbage) {
            gc();
        }

        return mKeys[index];
    }

    /**
     * 给定一个范围0. size()-1的索引，返回*SparseArray存储的indexth键值映射的值。
     *
     * 在升序中对应于索引的值被保证*与升序中的键相关，例如，valueAt(0)将返回与最小键和valueAt相关的值(size()-1)将返回与最大键相关的值。
     */
    @SuppressWarnings("unchecked")
    public E valueAt(int index) {
        if (mGarbage) {
            gc();
        }

        return (E) mValues[index];
    }

    /**
     * 给定一个范围0. size()-1的索引，为这个SparseArray存储的indexth键值映射设置一个新的*值。
     */
    public void setValueAt(int index, E value) {
        if (mGarbage) {
            gc();
        }

        mValues[index] = value;
    }

    /**
     * 返回该索引，其中{@link #keyAt}将返回指定的键值，如果指定的*键没有映射，则返回一个负数。
     */
    public int indexOfKey(int key) {
        if (mGarbage) {
            gc();
        }

        return ContainerHelpers.binarySearch(mKeys, mSize, key);
    }

    /**
     * 返回一个索引，其中{@link #valueAt}将返回指定的键值，如果没有键映射到指定值，则返回一个负数。
     * 要注意，这是一个线性搜索，不同于查找键，多个键可以映射到相同的值，而这只会找到其中一个。
     *
     * 注意，与大多数集合的{@code indexOf}方法不同，该方法使用{@code ==}而不是{@code equals}来比较值。
     *
     */
    public int indexOfValue(E value) {
        if (mGarbage) {
            gc();
        }

        for (int i = 0; i < mSize; i++)
            if (mValues[i] == value)
                return i;

        return -1;
    }

    /**
     * 从这个SparseArray中删除所有键值映射。
     */
    public void clear() {
        int n = mSize;
        Object[] values = mValues;

        for (int i = 0; i < n; i++) {
            values[i] = null;
        }

        mSize = 0;
        mGarbage = false;
    }

    /**
     * 将一个键/值对放入数组中，优化该数组中键大于所有现有键的情况。
     */
    public void append(int key, E value) {
        if (mSize != 0 && key <= mKeys[mSize - 1]) {
            put(key, value);
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();
        }

        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
        mValues = GrowingArrayUtils.append(mValues, mSize, value);
        mSize++;
    }

    /**
     * {@inheritDoc}
     * 该实现通过遍历其映射来组成一个字符串。
     * 如果此映射包含自身为值，则将出现字符串"(this Map)",防止死循环。
     *
     */
    @Override
    public String toString() {
        if (size() <= 0) {
            return "{}";
        }

        StringBuilder buffer = new StringBuilder(mSize * 28);
        buffer.append('{');
        for (int i=0; i<mSize; i++) {
            if (i > 0) {
                buffer.append(", ");
            }
            int key = keyAt(i);
            buffer.append(key);
            buffer.append('=');
            Object value = valueAt(i);
            if (value != this) {
                buffer.append(value);
            } else {
                buffer.append("(this Map)");
            }
        }
        buffer.append('}');
        return buffer.toString();
    }
}
